In a network with one-dimensional topology, the nodes are connected to form a chain. Typically, each node shall be connected to its direct two neighbours in the chain through so called first hop connections. In addition, each node may be connected to its direct neighbour's neighbours through so called second hop connections. Each node shall have a unique address or identity. Given a certain source address and destination address for a data unit, there exist multiple paths over which the data unit can be routed from source to destination. The number of possible routes from source to destination scales exponentially with the number of nodes in the network. Therefore, establishing an optimal path between source and destination poses a technical challenge.
Existing mechanism to route a data unit from a source node with source address to a destination node with destination address encompass the distance-vector routing protocol and the link-state routing protocol.
According to the distance-vector routing protocol, each node maintains a vector table of minimum distance to every other node. The distance in this context must be interpreted broadly and generally represents a cost for reaching the destination node, e.g. an amount of hops, delay, available bandwidth, etc. Periodically, each node distributes all or part of its routing table to its neighbours. Upon receipt of a data unit, the receiving node determines the route with minimum distance to the destination and as a result thereof the direction (or exit interface) that will be used for forwarding the data unit to the next node. More details on the distance-vector routing protocol are retrievable from Wikipedia via the URL:                http://en.wikipedia.org/wiki/Distance-vector_routing_protocol        
According to the link-state routing protocol, each node maintains a connectivity map to the rest of the network in the form of a graph. The only information shared between nodes is connectivity related, i.e. each node informs the network about its neighbours, enabling each node to independently determine which nodes are connected to which other nodes. Upon receipt of a data unit, the receiving node can determine the best logical path toward the destination of the data unit, and derive therefrom the exit interface for forwarding the data unit. More details on the link-state routing protocol are retrievable from Wikipedia via the URL:                http://en.wikipedia.org/wiki/Link-state_routing_protocol        
Both the distance-vector routing protocol and the link-state routing protocol require extensive exchange of information for the construction and maintenance of routing tables. The memory requirements for storing these routing tables, the overhead as a result of maintenance of these routing tables, and the time needed to search these routing tables when determining the next hop increase proportionally with the network size. In particular when the network topology imposes restrictions, like for instance with one-dimensional network topologies, the complexity of the existing routing mechanisms is too high.
It is an objective of the present invention to disclose a method and computer program products for routing data units that overcomes the above defined drawbacks of the existing routing protocols. More particularly, it is an objective of the present invention to teach a method and computer program products for routing in one-dimensional networks that avoids construction and maintenance of routing tables in the different nodes, and significantly reduces the time needed to route data units. It is a further objective to reduce the memory requirements on nodes in networks with a one-dimensional topology, and to make these memory requirements independent of the network size. It is a further objective to reduce the overall complexity for routing data units from source to destination in networks with a one-dimensional topology.